#include<Cart.h>
#include<math.h>
#include<iostream>
using namespace std;
Node* Cart::create() {
	vector<int> index_data;
	double label = 0.0;
	for (int i = 0; i < datas->getLen(); i++) {
		index_data.push_back(i);
		label += datas->getData(i).y;
	}
	label = label / ((double) datas->getLen());
	vector<pair<int, double> > splits;
	for (int j = 0; j < features->size(); j++) {
		Feature feature = (*features)[j];
		feature.setMode(1);
		for (int s = 0; s < feature.getValues().size(); s++) {
			pair<int, double> p(j, feature.getValues()[s]);
			splits.push_back(p);
		}
	}
	return createNode(index_data, splits, label);
}

Node* Cart::createNode(vector<int> index_data,
		vector<pair<int, double> > splits, double label) {
	Node* result = new Node();
	result->setLabel(label);
	for (int i = 0; i < index_data.size(); i++) {
		result->addData(index_data[i]);
	}
	if (minData >= index_data.size()) {
		result->setLeaf(true);
		return result;
	}
	double mseall = mse(index_data, label);
	if (mseall < epsoion) {
		result->setLeaf(true);
		return result;
	}
	//查看是否需要选择
	double minmin = -1.0;
	int minmin_index = 0;
	vector<int> left;
	vector<int> right;
	double min_c1 = 0.0;
	double min_c2 = 0.0;
	for (int m = 0; m < splits.size(); m++) {
		double c1 = 0.0;
		double c2 = 0.0;
		pair<int, double> spl = splits[m];
		split(index_data, spl.first, spl.second, left, right);
		double min = 0.0;
		if (left.size() > 0) {
			for (int i = 0; i < left.size(); i++) {
				c1 += datas->getData(left[i]).y;
			}
			c1 = c1 / ((double) left.size());
			min += mse(left, c1);
		}
		if (right.size() > 0) {
			for (int i = 0; i < right.size(); i++) {
				c2 += datas->getData(right[i]).y;
			}
			c2 = c2 / ((double) right.size());
			min += mse(right, c2);
		}
		if (minmin < 0 || minmin > min) {
			minmin = min;
			minmin_index = m;
			min_c1 = c1;
			min_c2 = c2;
		}
		left.clear();
		right.clear();
	}

	split(index_data, splits[minmin_index].first, splits[minmin_index].second,
			left, right);
	splits.erase(splits.begin() + minmin_index);
	if (left.size() > 0 && right.size() > 0) {
		result->getChildren().push_back(createNode(left, splits, min_c1));
		result->getChildren().push_back(createNode(right, splits, min_c2));
	}
	return result;
}

double Cart::mse(vector<int> index_data, double label) {
	double sum = 0.0;
	for (int i = 0; i < index_data.size(); i++) {
		sum += pow(datas->getData(index_data[i]).y - label, 2.0);
	}
	return sum;
}

void Cart::split(vector<int>& index_data, int j, double s, vector<int>& left,
		vector<int>& right) {
	for (int k = 0; k < index_data.size(); k++) {
		if ((*features)[j].getMode() == 0) {
			if (datas->getData(index_data[k]).x->get(j) == s) {
				left.push_back(index_data[k]);
			} else {
				right.push_back(index_data[k]);
			}
		} else {
			if (datas->getData(index_data[k]).x->get(j) < s) {
				left.push_back(index_data[k]);
			} else {
				right.push_back(index_data[k]);
			}
		}
	}
}

void Cart::print(Node* root) {
	if (NULL == root) {
		return;
	}
	for (int i = 0; i < root->getDatas().size(); i++) {
		cout << datas->getData((root->getDatas())[i]).y << ",";
	}
	cout << endl;
	for (int i = 0; i < root->getChildren().size(); i++) {
		print(root->getChildren()[i]);
	}
}
